/**
 * 
 */
package dp.passed;

/**
 * @author xyyi
 *
 */
public class NumberOfWaysToMakeChanges {

	public static int makeChangesRecursive(int money, int[] coins) {
		if (money == 0 || coins.length == 0)
			return 0;
		return makeChangesRecursiveHelper(money, coins, 0);
	}

	public static int makeChangesRecursiveHelper(int money, int[] coins,
			int currCoin) {
		if (money == 0)
			return 1;
		if (currCoin == coins.length)
			return 0;

		int ways = 0;
		int coin = coins[currCoin];
		for (int i = 0, size = money / coin; i <= size; i++) {
			ways = ways
					+ makeChangesRecursiveHelper(money - i * coin, coins,
							currCoin + 1);
		}

		return ways;
	}

	/**
	 * 
	 */
	public NumberOfWaysToMakeChanges() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[] coins = new int[] { 1, 2 };
		int money = 4;
		int expectedWays = 3;
		System.out
				.printf("countChange: example given in instructions: (ansower:expected) - (%d, %d)\n",
						makeChangesRecursive(money, coins), expectedWays);

		coins = new int[] { 5, 10, 20, 50, 100, 200, 500 };
		money = 300;
		expectedWays = 1022;
		System.out.printf(
				"countChange: sorted CHF: (ansower:expected) - (%d, %d)\n",
				makeChangesRecursive(money, coins), expectedWays);

		coins = new int[] { 5, 10, 20, 50, 100, 200, 500 };
		money = 301;
		expectedWays = 0;
		System.out.printf(
				"countChange: no pennies: (ansower:expected) - (%d, %d)\n",
				makeChangesRecursive(money, coins), expectedWays);

		coins = new int[] { 500, 5, 50, 100, 20, 200, 10 };
		money = 300;
		expectedWays = 1022;
		System.out.printf(
				"countChange: unsorted CHF: (ansower:expected) - (%d, %d)\n",
				makeChangesRecursive(money, coins), expectedWays);
	}
}
